package com.example.Arithmetic.Arithmetic;

/**
 * 日期：2024/1/1
 * 时间：12:37
 * 描述：钢条切割问题，求钢条最大价值
 * 动态规划求解
 */
public class CutRodProblem {
    public static void main(String[] args) {
        System.out.println(cut(new int[]{0, 1, 5, 8, 9}, 4));
    }

    private static int cut(int[] ints, int n) {
        int[] dp = new int[n+1];
        for (int i = 1; i < ints.length; i++) {
            for (int j = 1; j < n+1; j++) {
                if (j>=i) {
                    dp[j] = Math.max(dp[j], ints[i] + dp[j - i]);
                }
            }
        }
        return dp[ints.length-1];
    }
}
